package com.lw.leetcode.sort.c;

import com.lw.test.util.Utils;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * 218. 天际线问题
 *
 * @author liw
 * @version 1.0
 * @date 2022/10/19 9:42
 */
public class GetSkyline {

    public static void main(String[] args) {
        GetSkyline test = new GetSkyline();


        // {{2,10},{3,15},{7,12},{12,0},{15,10},{20,8},{24,0}}
//        int[][] arr = {{2, 9, 10}, {3, 7, 15}, {5, 12, 12}, {15, 20, 10}, {19, 24, 8}};

        // {{0,3},{5,0}}
//        int[][] arr ={{0,2,3},{2,5,3}};

        // [[1,3],[3,0]]
//        int[][] arr = {{1, 2, 1}, {1, 2, 2}, {1, 2, 3}, {2, 3, 1}, {2, 3, 2}, {2, 3, 3}};

        // [[9,55],[28,88],[54,97],[83,88],[87,80],[94,37],[96,27],[99,0]]
//        int[][] arr = {{9, 57, 55},{16, 96, 37},{17, 69, 49},{25, 77, 27},{28, 50, 62},{28, 53, 39},{28, 87, 88},{31, 59, 77},{34, 88, 70},{42, 51, 9},{43, 75, 25},{48, 65, 10},{54, 83, 97},{54, 60, 39},{56, 99, 27},{57, 80, 3},{69, 70, 23},{73, 94, 80},{79, 87, 17},{80, 94, 24}};

        // [[9,79],[13,84],[32,99],[38,79],[43,99],[81,79],[94,0]]
//        int[][] arr = {{9, 28, 79},{13, 34, 84},{17, 62, 9},{19, 29, 18},{19, 84, 19},{19, 33, 84},{22, 76, 76},{24, 44, 53},{27, 34, 3},{28, 62, 48},{31, 66, 69},{32, 38, 99},{33, 83, 8},{38, 94, 79},{39, 47, 2},{43, 81, 99},{47, 59, 77},{55, 68, 91},{58, 85, 63},{65, 81, 37}};

        int[][] arr = Utils.getArrSort(10000, 3, 1, 1000000000);


        List<List<Integer>> skyline = test.getSkyline(arr);
        System.out.println(skyline);
    }

    public List<List<Integer>> getSkyline(int[][] buildings) {
        TreeMap<Integer, Long> map = new TreeMap<>();
        for (int[] building : buildings) {
            int st = building[0];
            int end = building[1];
            int hight = building[2];
            Map.Entry<Integer, Long> entry = map.floorEntry(st);
            if (entry != null) {
                int si = entry.getKey();
                long value = entry.getValue();
                int ei = (int) (value >> 32);
                int hi = (int) value;
                if (ei > st) {
                    if (end < ei) {
                        if (hight > hi) {
                            if (si != st) {
                                map.put(si, ((long) st << 32) + hi);
                            }
                            map.put(st, ((long) end << 32) + hight);
                            map.put(end, value);
                        }
                        continue;
                    }
                    if (st == si) {
                        if (hight > hi) {
                            int t = find(map, st - 1, hight);
                            if (t != -1) {
                                map.put(t, ((long) ei << 32) + hight);
                                map.remove(st);
                            } else {
                                map.put(st, ((long) ei << 32) + hight);
                            }
                        }
                        st = ei;
                    } else {
                        if (hight > hi) {
                            map.put(si, ((long) st << 32) + hi);
                            map.put(st, ((long) ei << 32) + hight);
                        }
                        st = ei;
                    }
                }
            } else {
                entry = map.ceilingEntry(st);
                if (entry == null) {
                    map.put(st, ((long) end << 32) + hight);
                    continue;
                }
                int si = entry.getKey();
                if (end <= si) {
                    map.put(st, ((long) end << 32) + hight);
                    continue;
                }
                map.put(st, ((long) si << 32) + hight);
                st = si;
            }
            entry = map.ceilingEntry(st);
            while (entry != null) {
                int si = entry.getKey();
                if (end <= si) {
                    break;
                }
                long value = entry.getValue();
                int ei = (int) (value >> 32);
                int hi = (int) value;
                if (st < si) {
                    int item = Math.min(end, si);
                    int t = find(map, st - 1, hight);
                    t = t == -1 ? st : t;
                    map.put(t, ((long) item << 32) + hight);
                    st = item;
                    entry = map.ceilingEntry(st);
                    continue;
                }
                if (hight > hi) {
                    if (end <= ei) {
                        int t = find(map, st - 1, hight);
                        if (t != -1) {
                            map.put(t, ((long) end << 32) + hight);
                            map.remove(st);
                        } else {
                            map.put(st, ((long) end << 32) + hight);
                        }
                        if (end != ei) {
                            map.put(end, value);
                        }
                        break;
                    }
                    int t = find(map, st - 1, hight);
                    if (t != -1) {
                        map.put(t, ((long) ei << 32) + hight);
                        map.remove(st);
                    } else {
                        map.put(st, ((long) ei << 32) + hight);
                    }
                    st = ei;
                } else {
                    st = Math.min(end, ei);
                }
                if (st == end) {
                    break;
                }
                entry = map.ceilingEntry(st);
            }
            if (entry == null && st < end) {

                int t = find(map, st - 1, hight);
                if (t != -1) {
                    map.put(t, ((long) end << 32) + hight);
                    map.remove(st);
                } else {
                    map.put(st, ((long) end << 32) + hight);
                }
            }
        }

        List<List<Integer>> list = new ArrayList<>();

        int el = -1;
        for (Map.Entry<Integer, Long> entry : map.entrySet()) {
            int si = entry.getKey();
            long value = entry.getValue();
            int ei = (int) (value >> 32);
            int hi = (int) value;
            if (el != si && el != -1) {
                list.add(Arrays.asList(el, 0));
            }
            list.add(Arrays.asList(si, hi));
            el = ei;
        }
        if (el != -1) {
            list.add(Arrays.asList(el, 0));
        }
        return list;
    }

    private int find(TreeMap<Integer, Long> map, int st, int hight) {
        Map.Entry<Integer, Long> entry = map.floorEntry(st);
        if (entry == null) {
            return -1;
        }
        int si = entry.getKey();
        long value = entry.getValue();
        int ei = (int) (value >> 32);
        int hi = (int) value;
        if (ei == st + 1 && hi == hight) {
            return si;
        }
        return -1;
    }
}
